package test.oddevenlinkedlist;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public String getString() {
        StringBuilder builder = new StringBuilder();
        ListNode current = this;
        while (current.next != null) {
            builder.append(current.val).append(",");
            current = current.next;
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        ListNode head = null, current = null;
        for (int i = 0; i < 5; i++) {
            ListNode listNode = new ListNode(i + 1);
            if (i == 0) {
                head = listNode;
                current = listNode;
            } else {
                current.next = listNode;
                current = current.next;
            }

        }
        ListNode listNode = new ListNode().new Solution().oddEvenList(head);
        System.out.println(listNode);
    }

    class Solution {
        public ListNode oddEvenList(ListNode head) {

            if (head == null) {
                return null;
            }
            ListNode tail = head;
            int n = 1;
            while (tail.next != null) {
                tail = tail.next;
                n++;
            }
            ListNode current = head;
            ListNode firstEven = head.next;
            int num = n / 2;
//1234567  1357246
            for (int i = 0; i < num; i++) {
                //第一个偶数移到最后
                tail.next = firstEven;
                current.next = firstEven.next;
                firstEven.next = null;

                current = current.next;
                firstEven = current.next;
                tail = tail.next;
            }
            return head;
        }
    }
}
